// 递归
// 本质是：解决主问题时，发现相同子问题，解决主问题和子问题的方法相同 (主问题有可能就是子问题)
// 心理暗示：宏观看待递归问题，把递归函数当成黑盒，相信这个黑盒一定能完成任务
// 技巧：
//      找到重复子问题 -> 设计函数头
//      子问题是如何解决的 -> 函数体的书写
//      注意递归函数的出口 -> 关注问题不能分割的情况
// 拓展：如果一个题目可以用决策树画出来，那么也可以通过递归解决
// 二叉搜索树要用中序遍历去做
// 当 dfs 要做的事情较多时，可以定义全局变量帮助解决问题

// 例题 6：
// 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
//
//        叶子节点 是指没有子节点的节点。
//
//        示例 1：
//
//        输入：root = [1,2,3,null,5]
//        输出：["1->2->5","1->3"]
//        示例 2：
//
//        输入：root = [1]
//        输出：["1"]
//
//
//        提示：
//
//        树中节点的数目在范围 [1, 100] 内
//        -100 <= Node.val <= 100

// 解题思路：
// 使用二叉树的前序遍历即可
// 回溯时要考虑“恢复现场”

import java.util.ArrayList;
import java.util.List;

public class BinaryTreePaths {
    List<String> ret = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root, new StringBuilder());
        return ret;
    }
    public void dfs(TreeNode root, StringBuilder path){
        if(root == null) return;
        StringBuilder newPath = new StringBuilder(path);
        newPath.append(root.val);
        if(root.left == null && root.right == null){
            ret.add(newPath.toString());
        }
        newPath.append("->");
        dfs(root.left, newPath);
        dfs(root.right, newPath);
    }
}
